//
// Created by andrew on 2024/9/21.
//

#include <string>
#include <vector>
#include <unordered_set>

#include <iostream>
#include <gtest/gtest.h>


using namespace std;


// 最优解法
class Solution {
public:
    double findMedianSortedArrays(std::vector<int> nums1, std::vector<int> nums2) {
        int n = nums1.size();
        int m = nums2.size();
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
        return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
    }

private:
    int getKth(std::vector<int> nums1, int start1, int end1, std::vector<int> nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return std::min(nums1[start1], nums2[start2]);

        int i = start1 + std::min(len1, k / 2) - 1;
        int j = start2 + std::min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }
};





/*

 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int[] nums;
    int m = nums1.length;
    int n = nums2.length;
    nums = new int[m + n];
    if (m == 0) {
        if (n % 2 == 0) {
            return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
        } else {

            return nums2[n / 2];
        }
    }
    if (n == 0) {
        if (m % 2 == 0) {
            return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
        } else {
            return nums1[m / 2];
        }
    }

    int count = 0;
    int i = 0, j = 0;
    while (count != (m + n)) {
        if (i == m) {
            while (j != n) {
                nums[count++] = nums2[j++];
            }
            break;
        }
        if (j == n) {
            while (i != m) {
                nums[count++] = nums1[i++];
            }
            break;
        }

        if (nums1[i] < nums2[j]) {
            nums[count++] = nums1[i++];
        } else {
            nums[count++] = nums2[j++];
        }
    }

    if (count % 2 == 0) {
        return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
    } else {
        return nums[count / 2];
    }
}

 * */


// 归并之后再进行查找
class Solution1 {
public:
    double findMedianSortedArrays(std::vector<int> nums1, std::vector<int> nums2) {

        int m = nums1.size();
        int n = nums2.size();
        vector<int> nums(m + n);

        int count = 0;
        int i = 0, j = 0;
        // 归并排序
        while (count < (m + n)) {
            if (i == m) {
                nums[count++] = nums2[j ++];
                continue;
            }

            if (j == n) {
                nums[count++] = nums1[i ++];
                continue;
            }

            if (nums1[i] < nums2[j]) {
                nums[count++] = nums1[i++];
            } else {
                nums[count++] = nums2[j++];
            }

        }

        if (count % 2 == 0) {
            return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
        } else {
            return nums[count / 2];
        }
    }
};


/*

public double findMedianSortedArrays(int[] A, int[] B) {
    int m = A.length;
    int n = B.length;
    int len = m + n;
    int left = -1, right = -1;
    int aStart = 0, bStart = 0;
    for (int i = 0; i <= len / 2; i++) {
        left = right;
        if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
            right = A[aStart++];
        } else {
            right = B[bStart++];
        }
    }
    if ((len & 1) == 0)
        return (left + right) / 2.0;
    else
        return right;
}
*/

class Solution2 {
public:
    double findMedianSortedArrays(std::vector<int> nums1, std::vector<int> nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int len = m + n;

        int prefix = -1;
        int next = -1;

        int i = 0, j = 0;
        for (int count = 0; count <= len / 2; count ++) {
            // 最后一次Next指向 len / 2 但是prefix不指向
            prefix = next;

            if (i < m && (j >= n || nums1[i] < nums2[j])) {
                next = nums1[i++];
            } else {
                next = nums2[j++];
            }
        }
        // 如果是偶数，中位数为中间两个
        if ((len & 1) == 0) {
            return (prefix + next) / 2.0;
        } else {
            return next;
        }
    }



};








TEST(leetcode4, leetcode) {

    Solution1 solution_1;

    std::vector<int> nums1{1,3};
    std::vector<int> nums2{2};
    std::cout << solution_1.findMedianSortedArrays(nums1, nums2) << std::endl;


    ASSERT_EQ(1 , 1);
}



